#include <unordered_map>
#include <vector>
using namespace std;

void backtrace(vector<int> &nums, vector<vector<int>> &res,
               unordered_map<int, int> &stat, vector<int> &selected) {
  if (selected.size() == nums.size()) {
    res.push_back(selected);
    return;
  }
  for (auto x : nums) {
    if (stat.find(x) == stat.end()) {
      selected.push_back(x);
      stat[x] = 1;
      backtrace(nums, res, stat, selected);
      selected.pop_back();
      stat.erase(x);
    }
  }
}

vector<vector<int>> permute(vector<int> &nums) {
  // 记录结果
  vector<vector<int>> res;
  // 记录档当前状态
  unordered_map<int, int> stat;
  // 记录当前结果
  vector<int> selected;
  backtrace(nums, res, stat, selected);
  return res;
}

// 性能优化: 使用数组代替哈希表
void backtrace_1(vector<int> &nums, vector<vector<int>> &res, vector<int> &stat,
                 vector<int> &selected) {
  if (selected.size() == nums.size()) {
    res.push_back(selected);
    return;
  }
  for (int i = 0; i < nums.size(); ++i) {
    if (stat[i] == 0) {
      selected.push_back(nums[i]);
      stat[i] = 1;
      backtrace_1(nums, res, stat, selected);
      selected.pop_back();
      stat[i] = 0;
    }
  }
}

vector<vector<int>> permute_1(vector<int> &nums) {
  // 记录结果
  vector<vector<int>> res;
  // 记录档当前状态
  vector<int> stat(nums.size(), 0);
  for (int x : nums) {
    stat[x] = 0;
  }
  // 记录当前结果
  vector<int> selected;
  backtrace_1(nums, res, stat, selected);
  return res;
}